<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>排序算法的实现</title>
</head>

<body>
    <script>
        // 创建列表类
        class ArrayList {
            constructor() {
                this.array = []
            }

            // 将数据可以插入数组
            insert(item) {
                this.array.push(item)
            }

            // 转成字符串
            toString() {
                return this.array.join('-')
            }

            swip(m, n) {
                let temp = this.array[m]
                this.array[m] = this.array[n]
                this.array[n] = temp
            }
// --------------------------------------------------------------------------------------------------------------------------------

            // ---- 冒泡排序 ----
            bubbleSort() {
                const length = this.array.length
                for (let j = length - 1; j >= 0; j--) {
                    for (let i = 0; i < j; i++) {
                        const iItem = this.array[i];
                        if (this.array[i] > this.array[i + 1]) {
                            this.swip(i, i + 1)
                        }
                    }
                }
            }

            // ---- 冒泡排序的比较效率 ----
            // 如果有7个数字，那么比较次数为：6 + 5 + 4 + 3 + 2 + 1
            // 如果N个数据，那么比较次数为(N-1) + (N-2) + (N-3) + ... + 1
            // 因此比较次数为: N*(N-1)/2 = N²/2 - N/2

            // 通过以上公式，可以根据规则来推导：
            // 1. N²/2 - N/2 根据规则2，只保留最高阶项，保留了 N²/2
            // 2. N²/2 根据规则3，去除最高项的常量，变成了 N²
            // 因此冒牌排序的比较次数的大O表示法为 O(N²)

            // ---- 冒泡排序的交换次数 ----
            // 因为当次比较的概率为50%，因此可估算出交换次数为 N*(N-1)/4 = N²/4 - N/4
            // 通过以上公式，可以根据规则来推导：
            // 1. N²/4 - N/4 根据规则4，只保留最高阶项，保留了 N²/4
            // 2. N²/4 根据规则3，去除最高项的常量，变成了 N²
            // 因此冒牌排序的交换次数的大O表示法为 O(N²)
            

// --------------------------------------------------------------------------------------------------------------------------------

            // ---- 选择排序 ----
            selectionSort() {
                let length = this.array.length   
                for (let j = 0; j < length - 1; j++) {
                    let minIndex = j
                    for (let i = minIndex + 1; i < length; i++) {
                        let v = this.array[i]
                        if (this.array[i] < this.array[minIndex]) {
                            minIndex = i
                        }
                    }
                    this.swip(minIndex, j)
                }
            }

            // ---- 选择排序的比较效率（和冒泡排序一样） ----
            // 如果有7个数据，那么比较次数为：6 + 5 + 4 + 3 + 2 + 1
            // 如果N个数据，那么比较次数为(N-1) + (N-2) + (N-3) + ... + 1
            // 因此比较次数为: N*(N-1)/2 = N²/2 - N/2

            // 通过以上公式，可以根据规则来推导：
            // 1. N²/2 - N/2 根据规则2，只保留最高阶项，保留了 N²/2
            // 2. N²/2 根据规则3，去除最高项的常量，变成了 N²
            // 因此选择排序的比较次数的大O表示法为 O(N²)

            // ---- 选择排序的交换次数 ----
            // 如果有7个数据，那么就比较6次，如果有6个数据，那么就比较5次
            // 那么根据规律可推导出：
            // 1. 比较次数为：N - 1
            // 2. N-1 根据规则3，去除最高项的常量，变成了 N
            // 因此冒牌排序的交换次数的大O表示法为 O(N)


// --------------------------------------------------------------------------------------------------------------------------------

            // ---- 插入排序 ----
            insertionSort() {
                const length = this.array.length
                for (let i = 1; i < length; i++) {
                    const temp = this.array[i];
                    let j = i
                    while (this.array[j - 1] > temp && j > 0) {
                        this.array[j] = this.array[j - 1]
                        j--
                    }
                    this.array[j] = temp
                }
            }

            // ---- 插入排序的比较效率 ----
            // 第一次比较时，最多次数是1；第二次比较时，最多次数是2
            // 如果N个数据，那么最后一次的比较次数为N-1
            // 根据规律，可知最多比较次数为 1 + 2 + 3 + 4 + ... + N-1
            // 因此比较次数最多为: N*(N-1)/2
            // 但是，每次发现插入点之前，平均只有全部数据项的一半需要进行比较
            // 所以最终得出插入排序相对于其他冒泡、选择排序的比较次数是少了一半的
            // 因此插入排序的次数为：N*(N-1)/4


            // 通过以上公式，可以根据规则来推导：
            // 1. N²/4 - N/4 根据规则2，只保留最高阶项，保留了 N²/4
            // 2. N²/4 根据规则3，去除最高项的常量，变成了 N²
            // 因此选择排序的比较次数的大O表示法为 O(N²)

            // ---- 插入排序的交换次数 ----
            // 对于已经有序或基本有序的数据来说，插入排序效率相对来说会更高

// --------------------------------------------------------------------------------------------------------------------------------
            // ---- 希尔排序 ----
            // 希尔排序本质上是插入排序的升级版
            shellSort() {
                const length = this.array.length
                // 1. 初始化的增量 - 根据数组的一半来做间隔
                let gap = Math.floor(length/2)

                // 2. 当间隔小于1时，不再对数组做分割
                while(gap >= 1) {
                    // 3. 以当前gap作为间隔进行分组，对分组进行插入排序
                    // eg: 11 88 3 10 256 0 66
                        // 3.1 如果数组长度为7，那么gap为7/2=3.5，初始值为3
                        // 3.2 i = 3; i < 7; i++ 最终 i = 6 j = j-gap
                        // 3.3 temp = this.array[3]
                        // 3.4 j = 3 j++
                    for (let i = gap; i < length; i++) {
                        let temp = this.array[i]
                        let j = i
                        // 3.5 this.array[3 - 3] > this.array[3] && 3 > 3-1
                        // 3.6 11 > 10 && 3 > 3-1
                        // 3.7 this.array[3] = this.array[3-3] 
                        // 3.8 11和10替换
                        // 3.9 3 -= 3 ----> j = 0
                        // 3.10 temp[0] = this.array[3]
                        while(this.array[j - gap] > temp && j > gap - 1) {
                            this.array[j] = this.array[j - gap]
                            j -= gap
                        }
                        this.array[j] = temp
                    }
                    // 4. 增量变化 - gap在原来的基础上再分半进行间隔
                    gap = Math.floor(gap/2)
                }
            }
            // ---- 希尔排序的比较效率 ----
            // 最坏的情况，效率为O(N²)，通常要高于O(N²)
            // 甚至在合适的增量和某些数量N的情况下，还要好于快速排序

// --------------------------------------------------------------------------------------------------------------------------------
            // ---- 快速排序 ----
            // 快速排序本质上是冒泡排序的升级版
            // 快速排序最重要的思想是分治 - 分而治之

            // 1. 选择枢纽
            median(left, right) {
                let center = Math.floor((left+right)/2)
                if (this.array[left] > this.array[center]) {
                    this.swip(left, center)
                }
                if (this.array[left] > this.array[right]) {
                    this.swip(left, right)
                }
                if (this.array.center > this.array[right]) {
                    this.swip(center, right)
                }
                this.swip[center, right - 1]
                return this.array[right - 1]
            }
            quikSort() {
                this.quick(0, this.array.length - 1)
            }
            quick(left, right) {
                if (left >= right) return
                let i = left
                let j = right - 1 - 1
                let pivot = this.median(left, right)
                while (true) {
                    while (this.array[++i] < pivot) {}
                    while (this.array[--j] < pivot) {}
                    if (i < j) {
                        this.swip(i, j)
                    } else {
                        break
                    }
                }
                this.swip(i, right - 1)
                this.quick(left, i - 1)
                this.quick(i + 1, right)
            }
        }

        // 测试 
        let list = new ArrayList()
        list.insert(11)
        list.insert(88)
        list.insert(3)
        list.insert(10)
        list.insert(256)
        list.insert(0)
        list.insert(66)
        console.log(`初始数据：${list.toString()}`)

        // 1. 冒泡排序测试
        // list.bubbleSort()

        // 2. 选择排序测试
        // list.selectionSort()

        // 3. 插入排序测试
        // list.insertionSort()

        // 4. 希尔排序测试
        // list.insertionSort()

        // 5. 快速排序测试
        list.quikSort()
        console.log(list.toString())
    </script>
</body>

</html>